package l.l.w.leetcode.TrappingRainWater;

import java.awt.event.HierarchyBoundsAdapter;

/**
 * Created by llw on 2017/11/8.
 */
public class TrappingRainWater {

    public int trap(int[] height) {
        if(height == null || height.length <= 1)return 0;
        int result = 0;
        int pre = 0,maxValue = 0,min = 0, max = 0;
        for(int i = 0 ; i <  height.length; ++i){
            if(height[i] > height[maxValue]){
                maxValue = i;
            }
        }
        for(int i = 0 ; i < maxValue ;){
            pre = i;
            boolean isSuc = false;
            int j = i+1;
            for(; j <= maxValue; ++j){
                if(height[j] >= height[i]){
                    result += calculate(height,i,j,height[i]);
                    pre = i;
                    isSuc = true;
                    break;
                }
                if(height[i] > height[max]){
                    max = i;
                }
                if(height[i] < height[min]){
                    min = i;
                }
            }
            if(isSuc){
                i = j;
            }else{
                if(min == max) break;
            }
        }
        for(int i = height.length-1; i > maxValue; ){
            boolean isSuc = false;
            int j = i-1;
            for(; j >= maxValue; --j){
                if(height[j] >= height[i]){
                    result += calculate(height,j,i,height[i]);
                    isSuc = true;
                    break;
                }
                if(height[i] > height[max]){
                    max = i;
                }
                if(height[i] < height[min]){
                    min = i;
                }
            }
            if(isSuc){
                i = j;
            }else{
                if(min == max) break;
            }
        }
        return  result;
    }

    private int calculate(int[] height, int start, int end, int value) {
        int result = 0;
        for(int i = start+1; i < end; ++i){
            result += value - height[i];
        }
        return  result;
    }

    public static void main(String[] args) {
        int[] a = {0,1,0,2,1,0,1,3,2,1,2,1};
        int result = new TrappingRainWater().trap(a);
        System.out.println(result);
    }
}
